package com.company.disjSets;

import java.util.Random;

/**
 * Created by v on 16-12-13.
 */
public class Labyrinth {
    private boolean[][][] sides;
    private DisjSets disjSets;

    /**
     *
     * 对于一个n*m的迷宫，纵向边共(1+n)*(1+m)条，横向边也一样，
     * 因此我们用数组的最后一位表示纵横,z=0为横，z=1为纵
     *
     * @param rows 迷宫格子的行数
     * @param lines　迷宫格子的列数
     */
    public Labyrinth(int lines, int rows){
        sides =new boolean[lines+1][rows+1][2];
        disjSets=new DisjSets(rows*lines);

        //去除边框处露出来的边


        for(int i=0;i<=rows;i++){
            sides[lines][i][0]=true;
        }
        for(int i=0;i<=lines;i++){
            sides[i][rows][1]=true;
        }

        build(lines,rows);

        //打通入口与出口
        sides[0][0][1]=true;
        sides[lines][rows-1][1]=true;
    }

    //产生一个迷宫
    private void build(int lines,int rows){
        int[] randomNumbers=new int[rows*lines*2];

        //先生成一个包含所有边的编号的数组
        for(int i=0;i<randomNumbers.length;i++){
            randomNumbers[i]=i;
        }

        Random random=new Random();

        //对整个数组进行打乱处理
        for(int i=0;i<randomNumbers.length;i++){
            swap(randomNumbers,i,random.nextInt(randomNumbers.length));
        }

        //对迷宫的每一条边进行处理，若边的两头未连通，则删除边
        for(int i=0;i<randomNumbers.length;i++){
            int x=randomNumbers[i]%lines;
            int z=randomNumbers[i]/rows/lines;
            int y=(randomNumbers[i]-z*rows*lines)/lines;

            //对于位于边界的边，我们不处理
            if(y==0&&z==0){continue;}
            if(x==0&&z==1){continue;}

            //尝试打通这一条边
            if(z==0){
                int root1=disjSets.find(x+lines*y);
                int root2=disjSets.find(x+lines*(y-1));

                if(root1!=root2){
                    disjSets.union(root1,root2);
                    sides[x][y][z]=true;
                }
            }else {
                int root1=disjSets.find(x+lines*y);
                int root2=disjSets.find(x-1+lines*y);

                if(root1!=root2){
                    disjSets.union(root1,root2);
                    sides[x][y][z]=true;
                }
            }
        }
    }

    //交换两个值
    private final void swap(int[] array,int index1,int index2){
        int temp=array[index1];
        array[index1]=array[index2];
        array[index2]=temp;
    }

    //返回迷宫的某一个边是否被打通，若被打通则返回true
    public boolean getSide(int x,int y,int z){
        return sides[x][y][z];
    }

    public int getLines(){
        return sides.length;
    }

    public int getRows(){
        return sides[0].length;
    }
}
